#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 098. 验证二叉搜索树.py
@time: 2022/1/20 10:51
@desc: https://leetcode-cn.com/problems/validate-binary-search-tree/
> 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：
    - 节点的左子树只包含 小于 当前节点的数。
    - 节点的右子树只包含 大于 当前节点的数。
    - 所有左子树和右子树自身必须也是二叉搜索树。

@解题思路：
    1. dfs递归，必须验证上下界，否则会出现左子树的某右节点大于根节点的情况
    2. Ot(n), Os(n)
'''
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 错误解法，会出现左子树的某右节点大于根节点也被认为符合的情况
# class Solution(object):
#     def isValidBST(self, root):
#         """
#         :type root: TreeNode
#         :rtype: bool
#         """
#         if not root: return True
#         if root.left and not root.right:
#             if root.left.val>=root.val: return False
#         if not root.left and root.right:
#             if root.right.val <= root.val: return False
#         if root.left and root.right:
#             if root.left.val>=root.right.val or root.left.val>=root.val or root.right.val<=root.val: return False
#         return self.isValidBST(root.left) and self.isValidBST(root.right)

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        def dfs(root, lower, upper):
            if not root: return True
            if root.val <= lower: return False
            if root.val >= upper: return False
            return dfs(root.left, lower, root.val) and dfs(root.right, root.val, upper)

        return dfs(root, float('-inf'), float('inf'))

if __name__ == '__main__':
    root = TreeNode(2, left=TreeNode(1), right=TreeNode(3))
    res = Solution().isValidBST(root)
    print(res)